<html>
<head>
<title>Image To Hilbert curve</title>
</head>
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-2231125-7', 'auto');
  ga('send', 'pageview');
</script>
<script>

//http://www.icodeguru.com/Embedded/Hacker's-Delight/095.htm

var ctx = null
var x = 10, y = 10
var imgctx = null

var SZ = 256
var RATIO = 2
var WIDTH = RATIO*SZ
var HEIGHT = SZ
var MARGIN = 12 // for the SVG export


function start()
{
    imgctx = imgCanvas.getContext('2d')
    changedSize() // read ui config
   // drawImage()
   // makeCurve()
    
   // outToCanvas(path)

    imgCanvas.onmousedown = handleMouseDown
    document.onmouseup = handleMouseUp
    document.onmousemove = handleMouseMove
}

function drawImage()
{
    imgctx.fillStyle = 'white'
    imgctx.fillRect(0, 0, WIDTH, HEIGHT)
    if (fromImg.width >= fromImg.height) {
        // this crops the right side of the img
        var ir = fromImg.width / fromImg.height
        imgctx.drawImage(fromImg, 0, 0, WIDTH * ir/RATIO, HEIGHT)
    }
    else {
        // this crops the bottom of the img
        var ir = fromImg.width / fromImg.height
        imgctx.drawImage(fromImg, 0, 0, WIDTH, HEIGHT/ (ir/RATIO) )
    }
    makeCurve()
}


var pressedInCanvas = false
var didAdd = false;
function handleMouseDown(event) {
    didAdd = true
    pressedInCanvas = true
    addCircle(event.clientX, event.clientY)
}
function handleMouseMove(event) {
    if (pressedInCanvas) {
        didAdd = true
        addCircle(event.clientX, event.clientY)
        makeCurve()
    }
}
function handleMouseUp(event) {
    pressedInCanvas = false
    if (didAdd)
        makeCurve()
}

function addCircle(cx, cy) {
    var rect = imgCanvas.getBoundingClientRect()
    var x = cx - rect.left, y = cy - rect.top

    if (brBl.checked)
        imgctx.fillStyle = 'black'
    else if (brGr.checked)
        imgctx.fillStyle = 'gray'
    else if (brWh.checked)
        imgctx.fillStyle = 'white'
    
    imgctx.fillRect(x, y, 10, 10) // brush size
}

function triggerFileChanged() 
{
    if (editFileInput.files.length == 0)
        return
    var file = editFileInput.files[0]
    
    fromImg.onload = function() {
        drawImage()
       // makeCurve()
    }
    var reader = new FileReader();
    reader.onload = function(e) { 
        fromImg.src = e.target.result //, blob.type
    }
    reader.onerror = function(e) {
        console.log(e)
    }
    reader.readAsDataURL(file); // read as data URL since we want to put it in an img src

}

function triggerClear()
{
    imgctx.fillStyle = 'white'
    imgctx.fillRect(0, 0, WIDTH, HEIGHT)
    makeCurve()
}

var path = null

function makeCurve()
{
    preCheck()
    path = [] // global
    path.push([0,0])
    isOutside = false // global for both invocations if hilbertCurve

    path = hilbertCurve(0, path)
    if (RATIO >= 1)
        path = hilbertCurve(256, path)
    path = dedup(path);

    var text = outToSvg(path, false)
    showSvg.innerHTML = text

}

function distance(p1, p2) {
    var dx = p1[0] - p2[0]
    var dy = p1[1] - p2[1]
    return Math.sqrt(dx*dx+dy*dy)
}

function outToSvg(path, forExport) 
{
    var polyline = '<g><path id="pl1" style="fill:none;stroke:#000000;" d="M '
    var margin = forExport ? MARGIN : 0
    var dist = 0, count = 0
    
    for(i = 0; i < path.length; ++i) {
        if (path[i][0] == -1) {
            polyline += "M "
        }
        else {
            polyline += (path[i][0] + margin) + "," + (path[i][1] + margin) + " "
            if (i > 0 && path[i-1][0] != -1) {
                dist += distance(path[i], path[i-1])
                ++count
            }
        }
    }
    
    polyline += '"/></g>'
    
    var w = WIDTH*3 + 2*margin
    var h = HEIGHT*3 + 2*margin
    var szText = 'width="'+ w +'px" height="'+ h +'px"'
    if (forExport) {
        szText = 'width="297mm" height="210mm"'

        var len = 210/h*dist;
        console.log("Dist=" + Math.round(dist) + "px Length=" + Math.round(len) + "mm Count=" + count + "  wxh=" + w + "x" + h)
        showLen.innerHTML = "Length=" + (Math.round(len) / 1000) + " meters"
    }
    
    var text = '<svg xmlns="http://www.w3.org/2000/svg" version="1.1" ' + szText + ' viewBox="0 0 ' + w + ' ' + h + '">' +  polyline + '</svg>'
    return text
}


function dedup(path)
{
    var sz = path.length
    var cp = [path[0]]
    for(var i = 1; i < sz-1; ++i)
    {
        if ((path[i-1][0] == path[i][0] && path[i][0] == path[i+1][0]) || 
            (path[i-1][1] == path[i][1] && path[i][1] == path[i+1][1])) {
            continue
        }
        cp.push(path[i])
    }
    return cp
}


var hilbert = (function() {

  var pairs = [
    [[0, 3], [1, 0], [3, 1], [2, 0]],
    [[2, 1], [1, 1], [3, 0], [0, 2]],
    [[2, 2], [3, 3], [1, 2], [0, 1]],
    [[0, 0], [3, 2], [1, 3], [2, 3]]
  ];
  // d2xy and rot are from:
  // http://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms
  function rot(n, x, y, rx, ry) {
    if (ry === 0) {
      if (rx === 1) {
        x = n - 1 - x;
        y = n - 1 - y;
      }
      return [y, x];
    }
    return [x, y];
  }
  return {
    xy2d: function(x, y, z) {
      var quad = 0,
          pair,
          i = 0;
      while (--z >= 0) {
        pair = pairs[quad][(x & (1 << z) ? 2 : 0) | (y & (1 << z) ? 1 : 0)];
        i = (i << 2) | pair[0];
        quad = pair[1];
      }
      return i;
    },
    d2xy: function(z, t) {
      var n = 1 << z,
          x = 0,
          y = 0;
      for (var s = 1; s < n; s *= 2) {
        var rx = 1 & (t / 2),
            ry = 1 & (t ^ rx);
        var xy = rot(s, x, y, rx, ry);
        x = xy[0] + s * rx;
        y = xy[1] + s * ry;
        t /= 4;
      }
      return [x, y];
    }
  };
})();

var imgData = null
function preCheck() {
    imgData = imgctx.getImageData(0, 0, WIDTH, HEIGHT);
    
}

function check(crd, cf, xSampleOffset) 
{
    var x = crd[0]*cf + xSampleOffset, y = crd[1]*cf
    //return x + y < 256
    // this is slow
    //var imgData = imgctx.getImageData(x, y, 1, 1);
    var r = imgData.data[4*(y*WIDTH + x )]
    if (r < 50)
        return 2
    else if (r > 50 && r < 150)
        return 1
    return 0
}

var isOutside = false // used for adding stops in the path

function hilbertCurve(xSampleOffset, path) 
{
    //var mx = 1 << (level * 2)
    var coord =[0,0]
    var lvl = 5
    var seg = 10
    var count = 0
    var lastCheck = -1
    var i = 0
    var cf = 1 // check factor
    var first = true
    var avoided = 0
    var maxi = 0
    
    var showWhite = (modeSel.value == "iw")
    var coarse = (modeSel.value == "nwc")
    
    while(count < 540000)
    {
        var curCheck = check(coord, cf, xSampleOffset)
        var checkMod = coarse?1:0
        
        if (curCheck != lastCheck || first) 
        {
            first = false
            var prevCf = cf
            if (curCheck - checkMod == 0) {
                lvl = 6
                seg = 12
                cf = 4 
                maxi = 64*64
            }
            else if (curCheck - checkMod == 1) {
                lvl = 7
                seg = 6
                cf = 2 
                maxi = 128*128
            }
            else {
                lvl = 8
                seg = 3
                cf = 1
                maxi = 256*256
            }

            var relFactor = prevCf / cf 
            i = hilbert.xy2d( Math.floor(coord[0]*relFactor), Math.floor(coord[1]*relFactor), lvl)

            ++i // skip it to avoid a loop
        }
        else {
            ++i;
        }
        
        lastCoord = coord
        lastCheck = curCheck
        coord = hilbert.d2xy(lvl, i)
        
        var rx = coord[0]*seg + xSampleOffset*3
        var ry = coord[1]*seg
        
        var pushReal = rx < WIDTH * 3
        if (!showWhite)
            pushReal &= (curCheck != 0)
        
        if (pushReal)
        {
            isOutside = false
            path.push([rx,ry])
        }
        else {
            if (!isOutside) {
                path.push([-1,-1])
                isOutside = true;
            }
        }

        ++count;
        if (i >= maxi-1)
            break;

    }

    return path
  
}


function changedSize()
{
    var ratio = parseFloat(sizeSel.value)
    WIDTH = Math.round(HEIGHT * ratio)
    RATIO = WIDTH/HEIGHT
    imgCanvas.width = WIDTH
    showSize.innerHTML = "" + WIDTH + " x " + HEIGHT
    //triggerClear()
    drawImage()
}

var url = null
var downFilename = "hilbert_"

function triggerGenerateSvg()
{
    var text = outToSvg(path, true)
    var blob = new Blob([text], {type: "image/svg+xml"})
    if (url != null) {
        URL.revokeObjectURL(url)
    }
    url = URL.createObjectURL(blob)
    downLink.href = url
    var name = downFilename + Math.floor((Math.random() * 1000) + 1) + ".svg"
    downLink.innerHTML = name
    downLink.download = name
    downLink.style.visibility = "visible"
}

</script>
<style>
body {
    font-family: monospace;
    font-size: 120%;
}
#theCanvas {
    display:none
}
#imgCanvas {
    border: 1px black solid;
}
#fromImg {
    display:none
}
#ctrl {

}
#editFileInput {
    position: absolute;
    top: 10px;
    left: 100px;
}
#showSvg {
    position: absolute;
    top: 350px;
    margin:5px 0 5px 5px;
}
#clearBut {
    position: absolute;
    top: 40px;
    left: 100px;
    width: 60px;
}
#sizeSel {
    position: absolute;
    top: 40px;
    left: 170px;

}

#modeSel {
    position: absolute;
    top: 40px;
    left: 340px;
}
#downCont {
    position: absolute;
    top: 10px;
    left: 340px;
}
#downLink {
    visibility: hidden;
    margin: 0 0 0 10px;
}
#showSize {
    margin: 0 0 0 10px;
}
#showLen {
    position: absolute;
    top: 1120px;
}

</style>
<body onload="start()">
<div id="ctrl">
  <input id="brWh" type="radio" name="brush" value="white"><label for="brWh">White</label><br>
  <input id="brGr" type="radio" name="brush" value="gray"><label for="brGr">Gray</label><br>
  <input id="brBl" type="radio" name="brush" value="black" checked><label for="brBl">Black</label><br>
   <input id="editFileInput" type="file" onchange="return triggerFileChanged()">
   <input id="clearBut" type="button" value="Clear" onclick="triggerClear()">
   <select id="sizeSel" onchange="changedSize()">
    <option value="1.41428">1 x 1.414  A4 Ratio</option>
    <option value="2">1 x 2  Double</option>
    <option value="1">1 x 1  Square</option>
   </select>
   <select id="modeSel" onchange="makeCurve()">
    <option value="iw">Include White</option>
    <option value="nwf">No White, Fine</option>
    <option value="nwc">No White, Coarse</option>
   </select>
   <div id="downCont"><input type="button" value="Generate SVG" onclick="triggerGenerateSvg()"><a id="downLink" href=""></a></div>
</div>
<canvas id="imgCanvas" width="512" height="256"></canvas><span id="showSize"></span><br>
<div id="showSvg"></div><br>
<div id="showLen"></div>


<img id="fromImg" src="cat_test.png">
</body>

</html>